/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/majority-number
   @Language: C++
   @Datetime: 16-02-09 04:51
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers
	 * @return: The majority number
	 */
	/** Tips: Majority number occurs more than half
	 *
	 * */
	int majorityNumber(vector<int> nums) {
		// write your code here
		int a=-1, c=0;
		for(int i=0; i<nums.size(); ++i){
			if (c==0){
				a = nums[i];
				c = 1;
			}
			else c += (a==nums[i] ? 1:-1);
		}
		return a;
	}
};
